import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 困难
 * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 * 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
 * 输出：6
 * 1.转柱状图
 * 2.单调栈求柱状图中最大的矩形面积
 * @since 2023-09-12 9:29
 */
public class _085最大矩形 {
    public int maximalRectangle(char[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        //top[i][j] 以matrix[i][j]为底的柱状图高度
        int[][] top = new int[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(matrix[i][j] == '1'){    //连续的1
                    top[i][j] = (i == 0) ? 1 : top[i - 1][j] + 1;
                }
            }
        }
        int res = 0;
        for(int i = 0; i < n; i++){
            res = Math.max(res, getLargestRectangleArea(top[i]));
        }
        return res;
    }
    //单调栈求柱状图中最大的矩形面积
    public int getLargestRectangleArea(int[] height){
        Deque<Integer> stack = new LinkedList<>();
        int index, left, right;
        int res = 0;
        for(int i = 0; i < height.length; i++){
            while(!stack.isEmpty() && height[i] < height[stack.peek()]){
                index = stack.pop();
                if(stack.isEmpty()){
                    left = -1;
                }else{
                    left = stack.peek();
                }
                res = Math.max(res, (i - left - 1) * height[index]);
            }
            stack.push(i);
        }
        right = height.length;
        while(!stack.isEmpty()){
            index = stack.pop();
            if(stack.isEmpty()){
                left = -1;
            }else{
                left = stack.peek();
            }
            res = Math.max(res, (right - left - 1) * height[index]);
        }
        return res;
    }
}
